Traditionally, early mode violations in electronic circuit designs are corrected late in a design cycle. Correcting early mode violations has become a challenging problem in newer technologies. The most common solution to the fixing early-mode violations is to insert delay cells or pads along the fast paths to slow them down. When chips become larger with a corresponding increase in density, as guard-banding due to variations becomes more significant, and as clock domains and skew increases, the number of pads that require handling hold violations becomes unmanageable. The added padding, however, degrades the quality of the design with respect to area, power and routability.
Electronic designs must meet a host of constraints affecting the chip timing. Loosely speaking, timing requirements can be divided into late-mode and early-mode tests. For the late mode, some logic paths may be too slow and as a result, the expected value becomes available one cycle too late. A late-mode analysis is performed under the assumptions that clock signals are running fast and the data signals are running slow. For the early mode, the situation is reversed: paths are too fast, signals are available a cycle too early. The assumptions that are generally made include clock signals running at a slower rate while the data signals are too fast. Early-mode violations are also called “fast paths”, “short paths” or “hold violations”. It is possible for a single pin to have both early and late-mode timing violations.
As required by timing optimization, it is necessary to perform static timing analysis on a design to find the early and late slacks and directing the optimization to areas that have hold the violations. The method of selecting the most significant violation is generally achieved by creating a list of the violations ordered according to their severity, followed by a second order sort based on non-negative setup slack.
Static timing analysis (STA) algorithms operate by first levelizing the logic structure and breaking any loops in order to create a directed acyclic graph (timing graph). Each delay edge of the timing graph has a source node and sink node, and the sources of a node are the source nodes of its in-edges, while the sinks of a node are the sink nodes of their out-edges. Typically, a timing graph node is associated with each cell input and output pin, and delay edges associated with net source to sink connections and with input to output paths in cells through which signal transitions propagate. Modern designs can often contain millions of placeable objects, with corresponding timing graphs having millions, if not tens of millions of nodes. For each node, a corresponding arrival time, transition rate (slew), and required arrival time may be computed for both rising and falling transitions as well for both early and late mode analyses.
An arrival time (AT) represents the latest or earliest time at which a signal can transition due to the entire upstream fan-in cone. The slew value is the transition time (e.g., the time it takes the signal to transition from 10% of its final voltage to 90% of its final voltage) associated with a corresponding AT. And a required arrival time (RAT) represents the latest or earliest time at which a signal must transition due to timing constraints in the entire downstream fan-out cone. AT's are propagated forward in a levelized manner, starting from the chip primary input asserted (i.e., user-specified) arrival times, and ending at either primary output ports or intermediate storage elements. AT level numbers are integers assigned such that the AT level of a node is one greater than the largest AT level of any of its source nodes, or zero if it has no source nodes, and thus, the AT level of a node is the maximum number of delay edges between that node and any primary input of the design. For single fan-in cases,AT sink node=AT source node+delay from source to sink.
Whenever multiple signals merge, each fan-in contributes a potential arrival time computed asAT sink (potential)=AT source+delay.
Then, the maximum (late mode) or minimum (early mode) of all potential arrival times is retained. RATs are computed in a backward levelized manner starting from either asserted required arrival times at chip primary output pins, or from tests (e.g., setup or hold constraints) at internal storage devices. RAT level numbers are integers assigned such that the RAT level of a node is one greater than the largest RAT level of any of its sink nodes, or zero if it has no sink nodes, and thus the RAT level of a node is the maximum number of delay edges between that node and any primary output or timing constraint (setup or hold test) of the design. For single fan-out cases,RAT source node=RAT sink node−delay.
When multiple fan-outs merge (or a test is present), each fan-out (or test) contributes a prospective RAT, and then minimum (late mode) or maximum (early mode) required arrival time is retained. The difference between the arrival time and required arrival time (RAT−AT) in late mode, and (AT−RAT) in early mode, is referred to as slack. A positive slack implies that the current arrival time at a given node meets all downstream timing constraints, and a negative slack implies that the arrival time fails at least one such downstream timing constraint.
A single set of setup and hold tests for a node is normally not robust enough to ensure that chip timing achieves zero slack at a variety of different process and operating points.
Corner-based static timing has long been the bedrock technology for timing verification of integrated circuits. Timing of integrated circuits may vary due to processing variations. A corner refers to a set of process parameters/conditions (hereinafter “parameter”) that cause variations in the static timing. Processing variations can be classified into two groups: global variations and local variations. Conventionally, global variations, also referred to as chip-to-chip variations, are accommodated by a multi-corner timing. Specifically, each global variation is set to its three-standard deviation (3 sigma) extreme corners, one corner providing the fastest signal propagating checked in the fast chip timing analysis and another corner providing the slowest signal propagation checked in the slow chip timing analysis. Local variations, also referred to as on-chip variations, are modeled by creating a timing skew by making early path latency earlier and late path latency later. This is referred to as an early/late split. The early/late split is often introduced by “derating coefficients”, a set that derates the early and late timing.
A common solution to eliminating early-mode violations is by inserting delay cells or pads along the fast paths to slow them down. As chips become larger and denser, guardbanding due to variations increases together with the clock domains and skew, the number of pads that needs to be inserted increases, even though padding can degrade the quality of the design with respect to area, power and routability.
The general approach to handling early-mode violations is to work with a design that is nearly complete, that is, a design that has already been optimized for late-mode violations and electrical correctness, which has been placed and routed, and where a detailed electrical analysis, such as SPICE, has been completed. In this context, optimizations that correct early-mode violations must do so while preserving as much of the original design as possible. More specifically, such optimizations must not introduce a late-mode timing or electrical violation, nor are they to disturb the placement and routing more than necessary. Since many analysis functions cannot be updated incrementally, it is desirable to change the design in a way that does not invalidate such analyses.
Early-mode optimizations must operate in a highly-complex timing environment comprising multiple timing corners as well as early and late modes. (Timing corners define multiple environments in which a chip must operate, for example, at varying voltages or temperatures). The optimizations must be particularly robust and sensitive to these kinds of variations when evaluating the timing.
The problem of correcting early-mode violations is well known. A preferred method of correcting such violations is to insert delay cells (sometimes called “pads”) on the fast paths. The extra delay due to the pads can slow down a path sufficiently so that it is no longer too early. The process of adding pads is referred to as “early mode padding”.
Many publications focus on finding the optimal place to pad the paths, the optimal number of pads, and/or the optimal strength of pads to be inserted. Examples thereof include, for instance, work by T. Terrazzawa, “Hold Violation Improvement Method; Semiconductor Integrated Circuit and Program for Executing Hold Violation Improvement Method by Computer”, U.S. Patent Publication No. 2001/0007144; by Yigan Sun et. al, titled “Method and Apparatus for Fixing Hold-time Violations in a Circuit Design” in U.S. Patent Publication No. 2005/0268263; and by Chowder, S. et al., in a paper “Repeater insertion for concurrent setup and hold time violations with power-delay trade-off”, published in the Proceedings of ISPD, 2007.
An inherent difficulty when using pads to correct hold violations is that the pads consume both space on the chip image and power, and generally makes wiring the design more difficult. As long as hold violations were relatively rare, this was an acceptable trade-off. However, in current and future design environments, hold violations are more numerous as a result of the increasing number of clock domains, increased guard-banding related to process variation, and increased clock skew related to large chip sizes. In addition, more exacting power constraints and more dense use of silicon make the insertion of many thousands of delay pads problematic.
Moreover, this problem is compounded as a result of continuously advancing technologies. Area and power constraints make the reliance on only traditional padding techniques problematic. Because early-mode correction is done very late in the design, it is desirable to correct early-mode violations while causing minimum disruptions to other aspects of the design.
Therefore, there is a need for a method for correcting the aforementioned problems while achieving the goal of minimum design perturbation. Of particular importance is to create a new class of optimization of hold violations and a strategy for using them to encourage minimum design changes.